package com.hspedu.newData.dmsxl.动态规划.跳跃游戏;

import org.junit.Test;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-04-27 
 * @Version: 1.0
 */


public class LC45跳跃游戏Ⅱ {

    // 每次跳跃后，记录可以跳跃到的最远的距离和最近的距离
    // 在遍历这个范围，记录可以跳跃到的最远的距离就是新的最远的距离，新的最近的距离就是上一轮最远的距离
    public int jump(int[] nums) {

        // 左闭右开
        int start = 0;
        int end = 1;

        // 步数
        int ans = 0;

        int len = nums.length;

        while (end  < len){

            // 记录可以达到的最大的位置，下标从0开始，这个位置大于length就说明成功
            int masPose = 0;
            for (int i = start; i < end; i++) {
                masPose = Math.max(masPose,nums[i] + i);
            }

            start = end;
            end = masPose + 1;
            ans++;


        }
        return ans;
    }


    @Test
    public void test() {
        // 测试代码

        jump(new int[]{1,2,3});
        jump(new int[]{2,3,0,1,4});
    }

}
